/*
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。


链接：https://leetcode.cn/problems/3sum
 */
// https://blog.csdn.net/starflyyy/article/details/106955473

// 思路：先固定一个数字，然后寻找剩下两个数字，使用双指针；
// 先对数组排序，便于去重；
// 如果第一个数字>0，跳出循环；因为排序后，后面的数字都>0，三数之和不可能<0；
// 如果第一个数字与前面一个数字一样，跳过，因为之前得到的三元组肯定已经包含了
package LC0015;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution4 {
    public List<List<Integer>> threeSum(int[] nums) {// 总时间复杂度：O(n^2)
        // TODO 这里为什么是List<>? 可不可以用Set呢?
        // TODO list和set的区别???
        // TODO 这里为什么用Integer??

        List<List<Integer>> ans = new ArrayList<>();
        // TODO 为什么不用赋初始值为null?
        // TODO 为什么是ArrayList???

        // 对输入的数组进行校验，是否为空，是否长度不够
        if (nums.length <= 2) return ans;
        // TODO <=2不包含null的情况吗? 需要单独考虑吗?
            // 我认为不需要单独判断 nums==null 的情况了；

        // 对数组排序，便于后面的去重；
        Arrays.sort(nums); // O(nlogn) 时间复杂度? 空间复杂度?

        for (int i = 0; i < nums.length - 2; i++) { // O(n^2)
            // TODO 为什么是nums.length - 2
                // 因为三元组，第一个数字最多在倒数第三位

            // 先对第一个数字进行校验
            // 第一个数大于 0，后面的数都比它大，肯定不成立了；直接跳出for循环
            if (nums[i] > 0) break;
            // 和上一个数字重复，跳出本次循环，继续下一次循环
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            // TODO 为什么i > 0??
                // 否则[i - 1]越界
            // TODO Java使用break? continue?
            // TODO 这里和后一位数字比较，就不用判断i > 0了???

            // 剩余两数之和；
            int sum = -nums[i];
            // 确定两个指针的位置；
            int left = i + 1, right = nums.length - 1;

            while (left < right) {
                // 如果条件符合
                if (nums[left] + nums[right] == sum) {
                    // 拼装数组，加入List
                    ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));

                    // 现在要增加 left，减小 right
                    left++; right--; // 首先无论如何先要进行加减操作

                    // 但是不能重复，比如: [-2, -1, -1, -1, 3, 3, 3], i = 0, left = 1, right = 6, [-2, -1, 3] 的答案加入后，需要排除重复的 -1 和 3
                    // 元素相同再移动一位
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    // TODO 为什么是left-1? 左指针向右移动，不应该是+1？
                        // 因为先移动指针再回头比较的；
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (nums[left] + nums[right] < sum) {
                    left++;
                    // TODO 为什么移动左指针??
                        // 因为数组已经从小到大排序了。
                } else {  // nums[left] + nums[right] > target
                    right--;
                }
            }
        }
        return ans;
    }
}
